package com.gxc.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组 arr，该数组无序，其元素可正，可负，可0，再给定一个 k。
 * 求 arr 的所有子 数组中所有元素相加和为 k 的最长子数组长度。
 * 例如，arr=[1, -1, 5, -2, 3], k = 3。
 * 累加和为 3的最长子数组为[1,-1,5,-2]，所以结果返回 4。
 * 要求:时间复杂度0(N)，额外空间复杂度0(N)
 *
 * 解法：
 *
 */
public class MostEldestArray2 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, -1, 5, -2, 3};
        int aim = 3;

        System.out.println(process(arr, aim));
    }

    public static int process(int[] arr, int k) {
        int sum = 0;
        Map<Integer, Integer> sumMap = new HashMap<>();
        //统计中没有任何一个数据时，总和为0
        //非常重要
        sumMap.put(0, -1);

        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sumMap.containsKey(k - sum)) {
                max = Math.max(max, Math.abs(i -sumMap.get(k - sum)));
            }
            if (!sumMap.containsKey(sum)) {
                sumMap.put(sum, i);
            }
        }
        return max;
    }

}
